#include"Sorting.h"
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<vector>

void test(int _times,int _size=20000)
{
    /// 随机数种子，用于生成真正的随机数
    ///srand((unsigned int)time(nullptr));

    ///生成一定有序度的数组
    vector<int> arr,arr1,arr2,arr3;
    int i=0,j=0;
    for(i=0;i<_size;++i)
    {
	arr.push_back(_size-i);
    }
    for(i=0;i<_times;++i)///通过打乱次数控制有序度
    {
	/// index随机下标，用于随机访问数组元素
	int index1=(int)(rand()%arr.size()),index2=(int)(rand()%arr.size());
	int temp=arr[index1];
	arr[index1]=arr[index2];
	arr[index2]=temp;
    }
    arr1=arr;
    arr2=arr;
    arr3=arr;
    
    ///计算数组有序度
    double sum=0,p;
    for(i=0;i<_size;++i)
    {
	for(j=0;j<i;++j)
	{
	    if(arr[j]<arr[i])
		sum++;
	}
    }
    p=sum/(arr.size()*(arr.size()-1)/2);
    std::cout<<p<<std::endl;

    clock_t start,end;

    // start=clock();
    // heapsort(arr1);
    // end=clock();
    // std::cout<<"heapsort spents "<<(double)(end-start)/CLOCKS_PER_SEC<<" s"<<std::endl;

    start=clock();
    quicksort(arr);
    end=clock();
    std::cout<<"quicksort spents "<<(double)(end-start)/CLOCKS_PER_SEC<<" s"<<std::endl;

    start=clock();
    superquicksort(arr1);
    end=clock();
    std::cout<<"superquicksort spents "<<(double)(end-start)/CLOCKS_PER_SEC<<" s"<<std::endl;

    start=clock();
    quicksort(arr2);
    end=clock();
    std::cout<<"quicksort spents "<<(double)(end-start)/CLOCKS_PER_SEC<<" s"<<std::endl;

    start=clock();
    superquicksort(arr3);
    end=clock();
    std::cout<<"superquicksort spents "<<(double)(end-start)/CLOCKS_PER_SEC<<" s"<<std::endl;
}


int main(int argc,char*argv[])
{
    ///1705大约90%/10%有序度，155大约99%/1%有序度
    test(1705);
    test(1705);
    test(1705);
    test(1705);
    test(1705);
    return 0;
}
